//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.未分类;

import java.util.Arrays;
import java.util.HashMap;

public class demo_2563 {
    public demo_2563() {
    }

    public long countFairPairs(int[] nums, int lower, int upper) {
        HashMap<Integer, Integer> map = new HashMap();
        int n = nums.length;
        long count = 0L;

        for(int num : nums) {
            int value = (Integer)map.getOrDefault(num, 0);
            count += (long)value;

            for(int i = lower - num; i <= upper - num; ++i) {
                map.put(i, (Integer)map.getOrDefault(i, 0) + 1);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 7, 4, 4, 5};
        System.out.println(countFairPairs2(nums, 3, 6));
    }

    public static long countFairPairs2(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        int[] lowerNums = new int[n];
        int[] upperNums = new int[n];

        for(int i = 0; i < n; ++i) {
            int num = nums[i];
            int l = 0;
            int r = i - 1;

            while(l <= r) {
                int mid = l + (r - l) / 2;
                if (lowerNums[mid] > num) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            while(l >= 0 && l < i && num >= lowerNums[l] && num <= upperNums[l]) {
                ++count;
                ++l;
            }

            lowerNums[i] = lower - nums[i];
            upperNums[i] = upper - nums[i];
        }

        return (long)count;
    }
}
